Conjunto (programación)

En informática, un conjunto es una colección (contenedor) de ciertos valores, sin ningún orden concreto ni valores repetidos. Su correspondencia en las matemáticas sería el conjunto finito. Sin tener en cuenta la secuencia, ni el hecho de que no haya valores repetidos, se asemeja a una lista. Un conjunto puede verse como una cadena asociativa (array) (mapeado parcial) donde no se atiende al valor de cada par clave-valor.

Implementaciones

Los conjuntos pueden implementarse usando diversas estructuras de datos. Con una estructura de datos ideal se comprueba si un objeto se encuentra en el conjunto, además de activarse otras operaciones útiles tales como la iteración sobre todos los objetos del conjunto, la realización de uniones o intersecciones entre dos conjuntos, o la toma del complemento de un conjunto en algún dominio limitado. Cualquier estructura de datos en cadena asociativa puede usarse para implementar un conjunto, dejando que los juegos de claves sean los elementos del conjunto, e ignorando los valores. Gracias a su parecido con las series asociativas, los conjuntos se implementan habitualmente por los mismos medios, es decir, un árbol binario de búsqueda auto-balanceable para conjuntos ordenados (con O (log n) para la mayoría de operaciones), o una tabla hash para conjuntos no ordenados (que tienen O(1) en el caso promedio, pero O (n) en el peor caso, para la mayoría de operaciones). Es posible usar una tabla de hash lineal ordenada para crear conjuntos deterministamente ordenados. Otros métodos generalizados incluyen las cadenas (array). En particular, un subconjunto de enteros 1..n puede ser implementado de manera eficaz como en una matriz de bits con n bits, que además ofrece operaciones de unión e intersección muy eficaces. El filtro Bloom implementa un conjunto por probabilidad, por medio de una muy compacta representación, pero arriesgando una pequeña probabilidad de falsos positivos en interrogantes. Sin embargo, casi ninguna de estas estructuras de datos ofrece operaciones de conjuntos como de unión o de intersección de manera fiable. Para dichas operaciones existen otras estructuras de datos de conjunto más especializadas.

Soporte de lenguajes

Uno de los primeros lenguajes que soportaban conjuntos fue Pascal; muchos lenguajes lo incluyen ahora, ya sea en el núcleo del lenguaje o en una librería estándar. El Lenguaje de programación Java ofrece la interfaz Set para el soporte de conjuntos (donde lo implementa la clase Hash Set usando una tabla hash), y la sub-interfaz Sortease para dar soporte a conjuntos ordenados (implementado por la clase TreeSet por medio de un árbol de búsqueda binario). En C++, STL ofrece la clase "conjunto" para templates, que implementa a un conjunto ordenado usando un árbol de búsqueda binario; el STL de SGI ofrece la clase "hash_set", implementando conjuntos con una tabla de hash. Python tiene un tipo de conjunto incorporado, pero no un conjunto en sí.

Multiconjunto

Una variación del conjunto es el multiconjunto o bolsa, que es lo mismo que una estructura de datos de conjunto, pero que admite valores repetidos. Formalmente, un multiconjunto se puede considerar como una serie asociativa que mapea elementos únicos en enteros positivos, indicando la multiplicidad del elemento, aunque la implementación propiamente dicha pueda variar. En C++, la biblioteca de templates estándar (Standard Template Library) ofrece la clase "multiset" para los multiconjuntos ordenados, y la STL de SGI ofrece la clase "hash_multiset", que implementa conjuntos usando una tabla hash. Las colecciones de Apache Commons ofrecen la interfaz Bag y SortedBag para Java; además de implementar clases como HashBag y TreeBag, que son semejantes a otras implementaciones de conjuntos con nombres similares

Véase también

Datos: Q1514741